package leetcode;

import util.Tree;
import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0450.java
 * @Author : WangRuoyu
 * @Date 2023/11/15 21:27
 */


public class Q0450 {
    private TreeNode find(TreeNode node) {
        if (node.left == null) {
            return node;
        } else {
            return find(node.left);
        }
    }

    private void dfs(TreeNode root, int key, TreeNode father, boolean left) {
        if (root != null) {
            if (key == root.val) {
                TreeNode tmp;
                if (root.left == null && root.right == null) {
                    tmp = null;
                } else if (root.left != null && root.right == null) {
                    tmp = root.left;
                } else if (root.left == null) {
                    tmp = root.right;
                } else {
                    find(root.right).left = root.left;
                    tmp = root.right;
                }
                if (left) {
                    father.left = tmp;
                } else {
                    father.right = tmp;
                }
            } else if (key < root.val) {
                dfs(root.left, key, root, true);
            } else {
                dfs(root.right, key, root, false);
            }
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            TreeNode tmp;
            if (root.left == null && root.right == null) {
                tmp = null;
            } else if (root.left != null && root.right == null) {
                tmp = root.left;
            } else if (root.left == null) {
                tmp = root.right;
            } else {
                find(root.right).left = root.left;
                tmp = root.right;
            }
            return tmp;
        } else {
            dfs(root, key, null, true);
        }
        return root;
    }

    public static void main(String[] args) {
        Q0450 sl = new Q0450();
        int[] pre = {5, 3, 2, 4, 6, 7};
        int[] in = {2, 3, 4, 5, 6, 7};
        TreeNode root = Tree.createTreeByPreorderAndInorder(pre, in);
        sl.deleteNode(root, 7);
    }
}